package com.c2b.algorithm.leetcode.base.graph;

import java.util.*;

/**
 * Dijkstra 算法
 *
 * @author c2b
 * @since 2024/3/5 13:24
 */
public class _LC1976 {
    static class Solution {
        public int countPaths(int n, int[][] roads) {
            int mod = 1000000007;
            List<int[]>[] e = new List[n];
            for (int i = 0; i < n; i++) {
                e[i] = new ArrayList<>();
            }
            for (int[] road : roads) {
                int x = road[0];
                int y = road[1];
                int t = road[2];
                e[x].add(new int[]{y, t});
                e[y].add(new int[]{x, t});
            }


            // dis[i] 表示节点0到节点i的最短长度。初始时：dis[0]=0,其余dis[i]=∞(i>0)表示尚未计算出
            long[] dis = new long[n];
            Arrays.fill(dis, Long.MAX_VALUE);
            // ways[i] 表示节点0到点 i 的最短路径的条数，初始化时ways[0]=1,其他均为0
            int[] ways = new int[n];
            PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
            pq.offer(new long[]{0, 0});
            dis[0] = 0;
            while (!pq.isEmpty()) {
                long[] arr = pq.poll();
                long t = arr[0];
                int u = (int) arr[1];
                if (t > dis[u]) {
                    continue;
                }
                for (int[] next : e[u]) {
                    int v = next[0];
                    int w = next[1];

                    if (t + w < dis[v]) {
                        dis[v] = t + w;
                        ways[v] = ways[u];
                        pq.offer(new long[]{t + w, u});
                    } else if (t + w == dis[v]) {
                        ways[v] = (ways[u] + ways[v]) % mod;
                    }
                }
            }
            return ways[n - 1];
        }
    }
}
